{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Kth Largest Integer in the Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #divide-and-conquer #quickselect #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #分治 #快速选择 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kthLargestNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出数组中的第 K 大整数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串数组 <code>nums</code> 和一个整数 <code>k</code> 。<code>nums</code> 中的每个字符串都表示一个不含前导零的整数。</p>\n",
    "\n",
    "<p>返回 <code>nums</code> 中表示第 <code>k</code> 大整数的字符串。</p>\n",
    "\n",
    "<p><strong>注意：</strong>重复的数字在统计时会视为不同元素考虑。例如，如果 <code>nums</code> 是 <code>[\"1\",\"2\",\"2\"]</code>，那么 <code>\"2\"</code> 是最大的整数，<code>\"2\"</code> 是第二大的整数，<code>\"1\"</code> 是第三大的整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [\"3\",\"6\",\"7\",\"10\"], k = 4\n",
    "<strong>输出：</strong>\"3\"\n",
    "<strong>解释：</strong>\n",
    "nums 中的数字按非递减顺序排列为 [\"3\",\"6\",\"7\",\"10\"]\n",
    "其中第 4 大整数是 \"3\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [\"2\",\"21\",\"12\",\"1\"], k = 3\n",
    "<strong>输出：</strong>\"2\"\n",
    "<strong>解释：</strong>\n",
    "nums 中的数字按非递减顺序排列为 [\"1\",\"2\",\"12\",\"21\"]\n",
    "其中第 3 大整数是 \"2\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [\"0\",\"0\"], k = 2\n",
    "<strong>输出：</strong>\"0\"\n",
    "<strong>解释：</strong>\n",
    "nums 中的数字按非递减顺序排列为 [\"0\",\"0\"]\n",
    "其中第 2 大整数是 \"0\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i].length &lt;= 100</code></li>\n",
    "\t<li><code>nums[i]</code> 仅由数字组成</li>\n",
    "\t<li><code>nums[i]</code> 不含任何前导零</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-kth-largest-integer-in-the-array](https://leetcode.cn/problems/find-the-kth-largest-integer-in-the-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-kth-largest-integer-in-the-array](https://leetcode.cn/problems/find-the-kth-largest-integer-in-the-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"3\",\"6\",\"7\",\"10\"]\\n4', '[\"2\",\"21\",\"12\",\"1\"]\\n3', '[\"0\",\"0\"]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return str(sorted(list(map(int, nums)))[-k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return sorted(sorted(nums), key=len)[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        nums=[int(i) for i in nums]\n",
    "        nums.sort(reverse=True)\n",
    "        return str(nums[k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return str(sorted([int(i) for i in nums])[-k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        nums = [*map(int, nums)]\n",
    "        nums.sort(reverse=True)\n",
    "        return str(nums[k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        import heapq\n",
    "        pq = []\n",
    "        for n in nums:\n",
    "            heapq.heappush(pq, int(n))\n",
    "            if len(pq) > k:\n",
    "                heapq.heappop(pq)\n",
    "        \n",
    "        return str(pq[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        def cmp(s1: str, s2: str) -> int:\n",
    "            if len(s1) > len(s2):\n",
    "                return -1\n",
    "            elif len(s1) < len(s2):\n",
    "                return 1\n",
    "            else:\n",
    "                if s1 > s2:\n",
    "                    return -1\n",
    "                else:\n",
    "                    return 1\n",
    "        nums.sort(key=cmp_to_key(cmp))\n",
    "        return nums[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        nums = [int(i) for i in nums]\n",
    "        nums.sort(reverse = True)\n",
    "        return str(nums[k - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        res = [int(i) for i in nums]\n",
    "        res.sort(reverse=True)\n",
    "        return str(res[k - 1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        # 将字符串列表转换为整数列表并进行降序排序\n",
    "        int_list = [int(x) for x in nums]\n",
    "        int_list.sort(reverse=True)\n",
    "        \n",
    "        # 获取第 k 大的整数并将其转换为字符串\n",
    "        k_num = int_list[k - 1]\n",
    "        return str(k_num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        nums_int = []\n",
    "        for i in nums:\n",
    "            nums_int +=[int(i)]\n",
    "        nums_int.sort()\n",
    "        return str(nums_int[-k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        int_list = [int(i) for i in nums]\n",
    "        int_list.sort(reverse=True)\n",
    "        return str(int_list[k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        a = [int(x) for x in nums]\n",
    "        a = sorted(a, reverse =True)\n",
    "        return str(a[k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        num = [int(i) for i in nums]\n",
    "        num.sort()\n",
    "        return str(num[-k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        nums.sort(key = lambda x:int(x))\n",
    "        return nums[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        L = list(map(int, nums))\n",
    "        L.sort(reverse=True)\n",
    "        return str(L[k - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        nums1=[]\n",
    "        for i in range(len(nums)):\n",
    "            nums1.append(int(nums[i]))\n",
    "        nums1.sort(reverse=True)\n",
    "        return str(nums1[k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        nums = [int(x) for x in nums]\n",
    "        nums = sorted(nums)[::-1]\n",
    "        return str(nums[k-1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        nums.sort(key=int)\n",
    "        return nums[-k]\n",
    "        #return sorted(nums, key=int)[-k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        nums=[int(i) for i in nums]\n",
    "        nums.sort(reverse=True)\n",
    "        return str(nums[k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        # 自定义比较函数，在 s1 对应的整数较大时返回 -1，反之返回 1\n",
    "        def cmp(s1: str, s2: str) -> int:\n",
    "            # 首先比较字符串长度\n",
    "            if len(s1) > len(s2):\n",
    "                return -1\n",
    "            elif len(s1) < len(s2):\n",
    "                return 1\n",
    "            else:\n",
    "                # 长度相等时比较字符串字典序大小\n",
    "                if s1 > s2:\n",
    "                    return -1\n",
    "                else:\n",
    "                    return 1\n",
    "            \n",
    "        nums.sort(key=cmp_to_key(cmp))\n",
    "        return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        # 自定义比较函数，在 s1 对应的整数较大时返回 -1，反之返回 1\n",
    "        def cmp(s1: str, s2: str) -> int:\n",
    "            # 首先比较字符串长度\n",
    "            if len(s1) > len(s2):\n",
    "                return -1\n",
    "            elif len(s1) < len(s2):\n",
    "                return 1\n",
    "            else:\n",
    "                # 长度相等时比较字符串字典序大小\n",
    "                if s1 > s2:\n",
    "                    return -1\n",
    "                else:\n",
    "                    return 1\n",
    "            \n",
    "        nums.sort(key=cmp_to_key(cmp))\n",
    "        return nums[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        hp = []\n",
    "        for strnum in nums:\n",
    "            n = int(strnum)\n",
    "            hp.append(n)\n",
    "        hp.sort(reverse=True)\n",
    "        \n",
    "        return str(hp[k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        lists = []\n",
    "        # for i in nums:\n",
    "        #     lists.append(int(i))\n",
    "        # lists.sort()\n",
    "        # numss = []\n",
    "        # for i in lists:\n",
    "        #     numss.append(str(i))\n",
    "        nums.sort(key=int)\n",
    "        return nums[-k]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        n = len(nums)\n",
    "        int_n = [int(i) for i in nums]\n",
    "        heap = int_n[:k]\n",
    "        \n",
    "        heapq.heapify(heap)\n",
    "        #print(heap)\n",
    "        for i in range(k,n):\n",
    "            heapq.heappush(heap,int_n[i])\n",
    "            heapq.heappop(heap)\n",
    "        return str(heap[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq \n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        heap = []\n",
    "        for num in nums:\n",
    "            heapq.heappush(heap, int(num))\n",
    "            if len(heap)>k:\n",
    "                heapq.heappop(heap)\n",
    "\n",
    "        return str(heap[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        def cmp(stringOne: str, stringTwo: str):\n",
    "            if len(stringOne) > len(stringTwo):\n",
    "                return -1\n",
    "            elif len(stringTwo) > len(stringOne):\n",
    "                return 1\n",
    "            else:\n",
    "                if stringOne > stringTwo:\n",
    "                    return -1\n",
    "                return 1\n",
    "        nums.sort(key = functools.cmp_to_key(cmp))\n",
    "        return nums[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        nums.sort(key=lambda s:-int(s))\n",
    "        return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        nums.sort(key=lambda s:-int(s))\n",
    "        return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        # 将 nums 按照数值大小进行排序，但由于每个元素都是字符串，需要转换成 int 进行比较\n",
    "        sorted_nums = sorted(nums, key=int, reverse=True)\n",
    "        \n",
    "        # 返回第 k 大的数字（索引为 k-1，因为索引是从 0 开始的）\n",
    "        return sorted_nums[k - 1]\n",
    "\n",
    "# 示例\n",
    "s = Solution()\n",
    "print(s.kthLargestNumber([\"3\", \"6\", \"7\", \"10\"], 4))  # 输出应为 \"3\"\n",
    "print(s.kthLargestNumber([\"2\", \"21\", \"12\", \"1\"], 3))  # 输出应为 \"2\"\n",
    "print(s.kthLargestNumber([\"0\", \"0\"], 2))  # 输出应为 \"0\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        n = len(nums)\n",
    "        if k > n:\n",
    "            return \"\"\n",
    "        nums.sort(reverse=True, key=lambda x: int(x))\n",
    "        return nums[k-1]\n",
    "\n",
    "    def kthLargestNumber2(self, nums: List[str], k: int) -> str:\n",
    "        n = len(nums)\n",
    "        if k > n:\n",
    "            return \"\"\n",
    "\n",
    "        def partition(left, right):\n",
    "            # print(left, right)\n",
    "            # if left == right:\n",
    "            #     return left\n",
    "            ind = left\n",
    "            flag = int(nums[right])\n",
    "            for i in range(left, right):\n",
    "                if int(nums[i]) <= flag:\n",
    "                    nums[ind], nums[i] = nums[i], nums[ind]\n",
    "                    ind += 1\n",
    "            nums[ind], nums[right] = nums[right], nums[ind]\n",
    "            return ind\n",
    "\n",
    "        def find(start, end, k):\n",
    "            mid = partition(start, end)\n",
    "            if mid == k:\n",
    "                return nums[mid]\n",
    "            elif mid < k:\n",
    "                return find(mid+1, end, k)\n",
    "            else:\n",
    "                return find(start, mid-1, k)\n",
    "\n",
    "        return find(0, n-1, n-k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        nums.sort(key=lambda x:int(x))\n",
    "        return nums[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        def cmp(s1, s2):\n",
    "            if len(s1) > len(s2):\n",
    "                return -1\n",
    "            elif len(s1) < len(s2):\n",
    "                return 1\n",
    "            else:\n",
    "                if s1 > s2:\n",
    "                    return -1\n",
    "                else:\n",
    "                    return 1\n",
    "\n",
    "        nums.sort(key=cmp_to_key(cmp))\n",
    "        return nums[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        def compare(a:str,b:str):\n",
    "            if len(a) > len(b):\n",
    "                return -1\n",
    "            elif len(a) < len(b):\n",
    "                return 1\n",
    "            else:\n",
    "                return -1 if a>b else 1\n",
    "            \n",
    "        #选择排序\n",
    "        # for i in range(k):\n",
    "        #     for j in range(i+1,len(nums)):\n",
    "        #         if compare(nums[i],nums[j]) == nums[j]:\n",
    "        #             temp = nums[i]\n",
    "        #             nums[i] = nums[j]\n",
    "        #             nums[j] = temp\n",
    "        nums.sort(key=cmp_to_key(compare))\n",
    "                \n",
    "        return nums[k-1]\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        heap = list()\n",
    "        for num in nums:\n",
    "            heapq.heappush(heap, (len(num), num))\n",
    "            if len(heap) > k:\n",
    "                heapq.heappop(heap)\n",
    "        return min(heap)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        # 自定义比较函数，在 s1 对应的整数较大时返回 -1，反之返回 1\n",
    "        def cmp(s1: str, s2: str) -> int:\n",
    "            # 首先比较字符串长度\n",
    "            if len(s1) > len(s2):\n",
    "                return -1\n",
    "            elif len(s1) < len(s2):\n",
    "                return 1\n",
    "            else:\n",
    "                # 长度相等时比较字符串字典序大小\n",
    "                if s1 > s2:\n",
    "                    return -1\n",
    "                else:\n",
    "                    return 1\n",
    "            \n",
    "        nums.sort(key=cmp_to_key(cmp))\n",
    "        return nums[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        heap = []\n",
    "        for i in range(k):\n",
    "            heapq.heappush(heap, int(nums[i]))\n",
    "        for j in range(k, len(nums)):\n",
    "            if int(nums[j]) > heap[0]:\n",
    "                heapq.heapreplace(heap, int(nums[j]))\n",
    "        return str(heap[0])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "sys.set_int_max_str_digits(0)  # 大数的范围坑\n",
    "\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return str(sorted([int(num) for num in nums])[-k])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        heap = []\n",
    "        for i in range(k):\n",
    "            heapq.heappush(heap, int(nums[i]))\n",
    "        for j in range(k, len(nums)):\n",
    "            if int(nums[j]) > heap[0]:\n",
    "                heapq.heapreplace(heap, int(nums[j]))\n",
    "        return str(heap[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "\n",
    "        q = [-int(num) for num in nums]\n",
    "\n",
    "        heapq.heapify(q)\n",
    "        res=-1\n",
    "        for i in range(k):\n",
    "            if not q:return -1\n",
    "            res = heapq.heappop(q)\n",
    "\n",
    "        return str(-res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        nums.sort(key=lambda x: (len(x), x))\n",
    "        return nums[len(nums) - k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return sorted(nums, key = int)[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return sorted(nums, key=int)[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        # 理论上用最小栈更合适\n",
    "        arr = []\n",
    "        for sn in nums:\n",
    "            arr.append(int(sn))\n",
    "        arr.sort(reverse=True)\n",
    "        return str(arr[k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return sorted(nums, key=int)[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return sorted(nums, key=int)[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        n = len(nums)\n",
    "        nums.sort(key=lambda t:(len(t), t), reverse=True)\n",
    "\n",
    "        return nums[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return sorted(nums, key = int)[-k]\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        _list = []\n",
    "        for x in nums:\n",
    "            _list.append(int(x))\n",
    "        _list.sort(reverse=False)\n",
    "        #print(_list)\n",
    "        ans = str(_list[-k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        def quick_select(nums, k):\n",
    "            # randomly choose the partition \n",
    "            pivot = random.choice(nums)\n",
    "            big, equal, small = [], [], []\n",
    "            # set the elements > < = the pivot in big, small, equal\n",
    "            for string in nums:\n",
    "                if int(string) > int(pivot):\n",
    "                    big.append(string)\n",
    "                elif int(string) < int(pivot):\n",
    "                    small.append(string)\n",
    "                else:\n",
    "                    equal.append(string)\n",
    "            \n",
    "            if k<=len(big):\n",
    "                # k-th element in large\n",
    "                return quick_select(big, k)\n",
    "            elif len(nums)-len(small)<k:\n",
    "                # k-th element in small \n",
    "                return quick_select(small, k-len(nums)+len(small))\n",
    "            else:\n",
    "                # k-th element in equal \n",
    "                return pivot \n",
    "        \n",
    "        return quick_select(nums, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        hp = []\n",
    "        for strnum in nums[:k]:\n",
    "            n = int(strnum)\n",
    "            hp.append(n)\n",
    "        heapq.heapify(hp)\n",
    "        for strnum in nums[k:]:\n",
    "            n = int(strnum)\n",
    "            heapq.heappush(hp, n)\n",
    "            heapq.heappop(hp)\n",
    "        \n",
    "        return str(hp[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        _list = []\n",
    "        for x in nums:\n",
    "            _list.append(int(x))\n",
    "        _list.sort(reverse=False)\n",
    "        #print(_list)\n",
    "        ans = str(_list[-k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        temp=[]\n",
    "        for i in nums:\n",
    "            temp.append(int(i))\n",
    "        return str((sorted(temp))[-k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return sorted(nums, key=int, reverse=True)[k-1]\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "    def compare(self, num1, num2):\n",
    "        # num1 == num2 返回 0\n",
    "        # num1 > num2 返回 1\n",
    "        # num1 < num2 返回 -1\n",
    "        # 都是正数且不含前导0, 方便比较\n",
    "        if num1 == num2:\n",
    "            return 0\n",
    "        n1 = len(num1)\n",
    "        n2 = len(num2)\n",
    "        if n1 > n2:\n",
    "            return 1\n",
    "        if n1 < n2:\n",
    "            return -1\n",
    "        if num1 > num2:\n",
    "            return 1\n",
    "        else:\n",
    "            return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        _list = []\n",
    "        for x in nums:\n",
    "            _list.append(int(x))\n",
    "        _list.sort(reverse=False)\n",
    "        #print(_list)\n",
    "        ans = str(_list[-k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return str(sorted(list(map(int,nums)))[-k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return sorted(nums, key=int)[-k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "\n",
    "        return sorted(nums,key=int)[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        def dfs(nums,index):\n",
    "            l,insert,r = [],[],[]\n",
    "            ll,ii,rr = 0,0,0\n",
    "            p = choice(nums)\n",
    "            for s in nums:\n",
    "                if s > p:\n",
    "                    l.append(s)\n",
    "                    ll += 1\n",
    "                elif s == p:\n",
    "                    insert.append(s)\n",
    "                    ii += 1\n",
    "                else:\n",
    "                    r.append(s)\n",
    "                    rr += 1\n",
    "            #print(l,insert,r)\n",
    "            if ll >= index:\n",
    "                return dfs(l,index)\n",
    "            elif ll + ii < index:\n",
    "                return dfs(r,index-ll-ii)\n",
    "            return str(p)\n",
    "        return dfs([int(s) for s in nums],k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return sorted(nums, key=lambda x: int(x), reverse=True)[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return sorted(nums, key=lambda x:(len(x), x))[-k]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        # 自定义比较函数，在 s1 对应的整数较大时返回 -1，反之返回 1\n",
    "        def cmp(s1: str, s2: str) -> int:\n",
    "            # 首先比较字符串长度\n",
    "            if len(s1) > len(s2):\n",
    "                return -1\n",
    "            elif len(s1) < len(s2):\n",
    "                return 1\n",
    "            else:\n",
    "                # 长度相等时比较字符串字典序大小\n",
    "                if s1 > s2:\n",
    "                    return -1\n",
    "                else:\n",
    "                    return 1\n",
    "            \n",
    "        nums.sort(key=cmp_to_key(cmp))\n",
    "        return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        nums.sort(key=lambda x:int(x),reverse = True)\n",
    "        # print(nums)\n",
    "        return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return sorted(nums,key=lambda x:(len(x),x))[-k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        # 重复的数字在统计时会视为不同元素考虑。\n",
    "        # print(heapq.nlargest(k,nums))\n",
    "        newnums = []\n",
    "        for n in nums:\n",
    "            \n",
    "            newnums.append(int(n))\n",
    " \n",
    "        return str(heapq.nlargest(k,newnums)[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        # 定义自定义排序函数，目的是对nums中的字符串排序\n",
    "        def cmp(s1, s2):\n",
    "            if int(s1)>int(s2):\n",
    "                return 1\n",
    "            else:\n",
    "                return -1\n",
    "        nums.sort(key=cmp_to_key(cmp), reverse=True)\n",
    "        print(nums)\n",
    "        return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        x = heapq.nlargest(k, nums, key=int)\n",
    "        return str(x[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return sorted(nums, key = lambda k: (len(k), k))[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        def quick_select(arr, k):\n",
    "            n = len(arr)\n",
    "            base = arr[n//2]\n",
    "            big, equal, sml = [], [], []\n",
    "            for x in arr:\n",
    "                if x > base:\n",
    "                    big.append(x)\n",
    "                elif x < base:\n",
    "                    sml.append(x)\n",
    "                else:\n",
    "                    equal.append(x)\n",
    "            if len(big) >= k:\n",
    "                return quick_select(big, k)\n",
    "            if n - len(sml) < k:\n",
    "                return quick_select(sml, k - n + len(sml))\n",
    "            return equal[0]\n",
    "        ans = str(quick_select(list(map(int, nums)), k))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        nums.sort(key=int, reverse=True)\n",
    "        print(nums)\n",
    "        return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestNumber(self, nums: List[str], k: int) -> str:\n",
    "        return sorted(nums, key = lambda x: (len(x), x), reverse = True)[k-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
